Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 11665 - Chinese Ink / 11665.2.cpp
blob512853f45345f8ceaa9d95a5979d3640df7af81e
1 // Accepted
2 using namespace std;
3 #include <algorithm>
4 #include <iostream>
5 #include <iterator>
6 #include <numeric>
7 #include <sstream>
8 #include <fstream>
9 #include <cassert>
10 #include <climits>
11 #include <cstdlib>
12 #include <cstring>
13 #include <string>
14 #include <cstdio>
15 #include <vector>
16 #include <cmath>
17 #include <queue>
18 #include <deque>
19 #include <stack>
20 #include <list>
21 #include <map>
22 #include <set>
24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
26 #define D(x) cout << #x " is " << x << endl
28 #define EPS 1e-9
30 typedef pair<int, int> point;
31 typedef vector< point > polygon;
33 vector< polygon > polygons;
35 const int MAXN = 50;
36 int p[MAXN];
38 int find(int u) {
39 return p[u] == u ? u : p[u] = find(p[u]);
42 void link(int u, int v) {
43 if (find(u) != find(v)) {
44 p[find(u)] = find(v);
48 // Polar angle
49 // Returns an angle in the range [0, 2*Pi) of a given Cartesian point.
50 // If the point is (0,0), -1.0 is returned.
51 // REQUIRES:
52 // include math.h
53 // define EPS 0.000000001, or your choice
54 // P has members x and y.
55 double polarAngle( point p ) {
56 double x = p.first, y = p.second;
57 if(fabs(x) <= EPS && fabs(y) <= EPS) return -1.0;
58 if(fabs(x) <= EPS) return (y > EPS ? 1.0 : 3.0) * acos(0);
59 double theta = atan(1.0 * y / x);
60 if(x > EPS) return(y >= -EPS ? theta : (4*acos(0) + theta));
61 return(2 * acos( 0 ) + theta);
64 //Point inside polygon
65 // Returns true iff p is inside poly.
66 // PRE: The vertices of poly are ordered (either clockwise or
67 // counter-clockwise.
68 // POST: Modify code inside to handle the special case of "on
69 // an edge".
70 // REQUIRES:
71 // polarAngle()
72 // include math.h
73 // include vector
74 // define EPS 0.000000001, or your choice
75 bool pointInPoly( point p, const polygon &poly ) {
76 int n = poly.size();
77 double ang = 0.0;
78 for(int i = n - 1, j = 0; j < n; i = j++){
79 point v( poly[i].first - p.first, poly[i].second - p.second );
80 point w( poly[j].first - p.first, poly[j].second - p.second );
81 double va = polarAngle(v);
82 double wa = polarAngle(w);
83 double xx = wa - va;
84 if(va < -0.5 || wa < -0.5 || fabs(fabs(xx)-2*acos(0)) < EPS){
85 // POINT IS ON THE EDGE
86 return true;
87 assert( false );
88 ang += 2 * acos( 0 );
89 continue;
91 if( xx < -2 * acos( 0 ) ) ang += xx + 4 * acos( 0 );
92 else if( xx > 2 * acos( 0 ) ) ang += xx - 4 * acos( 0 );
93 else ang += xx;
95 return( ang * ang > 1.0 );
100 Returns true if point (x, y) lies inside (or in the border)
101 of box defined by points (x0, y0) and (x1, y1).
103 bool point_in_box(double x, double y,
104 double x0, double y0,
105 double x1, double y1){
106 return
107 min(x0, x1) <= x && x <= max(x0, x1) &&
108 min(y0, y1) <= y && y <= max(y0, y1);
113 Returns the cross product of the segment that goes from (x1, y1) to (x3, y3)
114 with the segment that goes from (x1, y1) to (x2, y2)
116 int direction(int x1, int y1, int x2, int y2, int x3, int y3) {
117 return (x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1);
121 Finds the intersection between two segments (Not infinite
122 lines!)
123 Segment 1 goes from point (x0, y0) to (x1, y1).
124 Segment 2 goes from point (x2, y2) to (x3, y3).
126 (Can be modified to find the intersection between a segment
127 and a line)
129 Handles the case when the 2 segments are:
130 *Parallel but don't lie on the same line (No intersection)
131 *Parallel and both lie on the same line (Infinite
132 *intersections or no intersections)
133 *Not parallel (One intersection or no intersections)
135 Returns true if the segments do intersect in any case.
137 bool segment_segment_intersection(int x1, int y1,
138 int x2, int y2,
140 int x3, int y3,
141 int x4, int y4){
143 int d1 = direction(x3, y3, x4, y4, x1, y1);
144 int d2 = direction(x3, y3, x4, y4, x2, y2);
145 int d3 = direction(x1, y1, x2, y2, x3, y3);
146 int d4 = direction(x1, y1, x2, y2, x4, y4);
147 bool b1 = d1 > 0 and d2 < 0 or d1 < 0 and d2 > 0;
148 bool b2 = d3 > 0 and d4 < 0 or d3 < 0 and d4 > 0;
149 if (b1 and b2) return true;
150 if (d1 == 0 and point_in_box(x1, y1, x3, y3, x4, y4)) return true;
151 if (d2 == 0 and point_in_box(x2, y2, x3, y3, x4, y4)) return true;
152 if (d3 == 0 and point_in_box(x3, y3, x1, y1, x2, y2)) return true;
153 if (d4 == 0 and point_in_box(x4, y4, x1, y1, x2, y2)) return true;
154 return false;
157 bool polygonsIntersect(const polygon &a, const polygon &b) {
158 int na = a.size(), nb = b.size();
159 for (int i = 0; i < na; ++i) {
160 if (pointInPoly(a[i], b)) return true;
162 for (int i = 0; i < nb; ++i) {
163 if (pointInPoly(b[i], a)) return true;
166 for (int i = 0; i < na; ++i) {
167 for (int j = 0; j < nb; ++j) {
168 int xa1 = a[i].first, ya1 = a[i].second;
169 int xa2 = a[(i + 1) % na].first, ya2 = a[(i + 1) % na].second;
170 int xb1 = b[j].first, yb1 = b[j].second;
171 int xb2 = b[(j + 1) % nb].first, yb2 = b[(j + 1) % nb].second;
172 if (segment_segment_intersection(xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2)) {
173 return true;
179 return false;
183 void solve() {
184 int n = polygons.size();
185 for (int i = 0; i < n; ++i) {
186 p[i] = i;
189 for (int i = 0; i < n; ++i) {
190 for (int j = i + 1; j < n; ++j) {
191 if (polygonsIntersect(polygons[i], polygons[j])) {
192 link(i, j);
196 set<int> ans;
197 for (int i = 0; i < n; ++i) {
198 ans.insert(find(i));
200 cout << ans.size() << endl;
204 int main(){
205 int n;
206 while (cin >> n) {
207 if (n == 0) break;
208 string s; getline(cin, s);
209 polygons.clear();
210 for (int i = 0; i < n; ++i){
211 polygons.push_back(polygon());
212 getline(cin, s);
213 stringstream sin(s);
214 int x, y;
215 while (sin >> x >> y) {
216 polygons.back().push_back(point(x, y));
218 assert(polygons.back().size() >= 3);
220 assert(polygons.size() == n);
222 solve();
224 return 0;